package algorithm

// 二叉树是一个有序的树 -> 而树是一个集

// binaryTreeImpl 二叉树接口
type binaryTreeImpl interface {
	SetLeftNode(value string) *binaryTree  // 设置左子叶节点
	SetRightNode(value string) *binaryTree // 设置右子叶节点
	checkFull()                            // 校验当前节点是否为满节点
	GetLeftNode() *binaryTree              // 获取左子叶节点
	GetRightNode() *binaryTree             // 获取右子叶节点
}

// binaryTree 二叉树结构体
type binaryTree struct {
	Value     string      `json:"value"`     // 节点值
	LeftNode  *binaryTree `json:"leftNode"`  // 左子叶节点
	RightNode *binaryTree `json:"rightNode"` // 右子叶节点
	Full      bool        `json:"full"`      // 是否满节点
}

// CreateBinaryTree 创建二叉树
func CreateBinaryTree(value string) *binaryTree {
	return &binaryTree{Value: value, LeftNode: nil, RightNode: nil, Full: true}
}

// SetLeftNode 设置左子叶节点
// 返回左子节点
func (the *binaryTree) SetLeftNode(value string) *binaryTree {
	the.LeftNode = &binaryTree{Value: value, LeftNode: nil, RightNode: nil, Full: true}
	the.checkFull()
	return the.LeftNode
}

// SetRightNode 设置右子叶节点
// 返回右子节点
func (the *binaryTree) SetRightNode(value string) *binaryTree {
	the.RightNode = &binaryTree{Value: value, LeftNode: nil, RightNode: nil, Full: true}
	the.checkFull()
	return the.RightNode
}

// checkFull 校验当前节点是否为满节点
// 子节点双方都为空或双方都不为空,则表示当前节点为满节点
// 判断满二叉树则只需要判断所有的full为true即可
// 判断为完全二叉树,则只需要依据深度 - 1 判断所有full为true即可
func (the *binaryTree) checkFull() {
	the.Full = (nil != the.LeftNode && nil != the.RightNode) || (nil == the.LeftNode && nil == the.RightNode)
}

// GetLeftNode 获取左子叶节点
func (the *binaryTree) GetLeftNode() *binaryTree {
	return the.LeftNode
}

// GetRightNode 获取右子叶节点
func (the *binaryTree) GetRightNode() *binaryTree {
	return the.RightNode
}
